package leetcode.offer0066;

import java.util.HashMap;
import java.util.Map;

public class MapSum {

	Node root;

	class Node {
		Node[] character;
		int prfixSum;
		int val;

		public Node() {
			character = new Node[26];
		}

		public void add(String key, int val) {
			char[] word = key.toCharArray();
			Node node = this;
			for (char c : word) {
				int index = c - 'a';
				if (node.character[index] == null) {
					node.character[index] = new Node();
				}
				node.character[index].prfixSum += val;
				node = node.character[index];
			}
			node.val += val;
		}

		public int query(String prefix) {
			char[] word = prefix.toCharArray();
			Node node = this;
			for (char c : word) {
				int index = c - 'a';
				if (node.character[index] == null) {
					return 0;
				}
				node = node.character[index];
			}
			return node.prfixSum;
		}

		public int queryVal(String prefix) {
			char[] word = prefix.toCharArray();
			Node node = this;
			for (char c : word) {
				int index = c - 'a';
				if (node.character[index] == null) {
					return 0;
				}
				node = node.character[index];
			}
			return node.val;
		}

	}

	Map<String, Integer> map;

	public MapSum() {
		root = new Node();
		map = new HashMap<>();
	}

	public void insert(String key, int val) {
		root.add(key, val - map.getOrDefault(key, 0));
//		root.add(key, val - root.queryVal(key));
		map.put(key, val);
	}

	public int sum(String prefix) {
		return root.query(prefix);
	}

	public static void main(String[] args) {
		MapSum mapSum = new MapSum();
		mapSum.insert("apple", 3);
		int a = mapSum.sum("ap"); // return 3 (apple = 3)
		mapSum.insert("app", 2);
		int b = mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)
		System.out.println(a);
		System.out.println(b);
	}

}
